17.5.5.1 Bit-Counting

Calc does not include a built-in function for counting the number of “one” bits in a binary integer. It’s easy to invent one using b u to convert the integer to a set, and V # to count the elements of that set; let’s write a function that counts the bits without having to create an intermediate set.

(defmath bcount ((natnum n))
  (interactive 1 "bcnt")
  (let ((count 0))
    (while (> n 0)
      (if (oddp n)
          (setq count (1+ count)))
      (setq n (lsh n -1)))
    count))

When this is expanded by defmath, it will become the following Emacs Lisp function:

(defun calcFunc-bcount (n)
  (setq n (math-check-natnum n))
  (let ((count 0))
    (while (math-posp n)
      (if (math-oddp n)
          (setq count (math-add count 1)))
      (setq n (calcFunc-lsh n -1)))
    count))

If the input numbers are large, this function involves a fair amount of arithmetic. A binary right shift is essentially a division by two; recall that Calc stores integers in decimal form so bit shifts must involve actual division.

To gain a bit more efficiency, we could divide the integer into n-bit chunks, each of which can be handled quickly because they fit into Lisp integers. It turns out that Calc’s arithmetic routines are especially fast when dividing by an integer less than 1000, so we can set n = 9 bits and use repeated division by 512:

(defmath bcount ((natnum n))
  (interactive 1 "bcnt")
  (let ((count 0))
    (while (not (fixnump n))
      (let ((qr (idivmod n 512)))
        (setq count (+ count (bcount-fixnum (cdr qr)))
              n (car qr))))
    (+ count (bcount-fixnum n))))

(defun bcount-fixnum (n)
  (let ((count 0))
    (while (> n 0)
      (setq count (+ count (logand n 1))
            n (lsh n -1)))
    count))

Note that the second function uses defun, not defmath. Because this function deals only with native Lisp integers (“fixnums”), it can use the actual Emacs + and related functions rather than the slower but more general Calc equivalents which defmath uses.

The idivmod function does an integer division, returning both the quotient and the remainder at once. Again, note that while it might seem that ‘(logand n 511)’ and ‘(lsh n -9)’ are more efficient ways to split off the bottom nine bits of n, actually they are less efficient because each operation is really a division by 512 in disguise; idivmod allows us to do the same thing with a single division by 512.